package lcr;

public class Test0040 {
}

class Solution0040_1 {
    public int maximalRectangle(String[] matrix) {
        int length = matrix.length;
        if (length==0) return 0;

        int width = matrix[0].length(),ans = 0;
        int[] heights = new int[width];

        for (String s : matrix) {
            char[] charArray = s.toCharArray();
            for (int i = 0; i < width; i++) {
                heights[i] = charArray[i]=='1'?heights[i]+1:0;
            }
            ans = Math.max(ans, largestRectangleArea(heights));
        }

        return ans;
    }

    private int largestRectangleArea(int[] heights) {
        int length = heights.length;
        int[] stack = new int[length + 1];
        stack[0] = -1;
        int index = 0, ans = 0;
        for (int i = 0; i < length; i++) {
            while (stack[index]>=0&&heights[i] < heights[stack[index]]){
                ans = Math.max(ans, heights[stack[index--]] * (i - stack[index] - 1));
            }
            stack[++index] = i;
        }

        while (stack[index] != -1) {
            ans = Math.max(ans, heights[stack[index--]] * (length - stack[index] - 1));
        }
        return ans;
    }
}
